The present invention relates to a method for correcting and detecting errors, and is particularly concerned with a single error correcting, double error detecting, and single b bit block error detecting method which is suitable for the expansion of coded data length and large scale integration (LSI).
In a conventional storage using IC memories, IC memories in which input and output data of single bit configuration is stored have been mostly used to reduce the pin number of the IC memory package and increase the packaging density. However, in accordance with the development of the technique for highly integrated IC memories, use of IC memories in which input and output data consisting of several (b) bits is increasing. In such an IC memory of b bit configuration, an error may occur in the block of b bits which is output from the IC memory in case of an IC memory failure. Even in conventional IC memory of single bit configuration, an error may also occur when the driver which drives b number (b bits) of IC memories in common is out of order and when the driver IC and the receiver IC of b bit configuration which drives and receives the input and output of the IC memory, respectively, are out of order.
Therefore, a method for correcting and detecting errors using the SEC-DED-SbED code (Single Error Correcting-Double Error Detecting-Single b bit byte Error Detecting Code) has been proposed which has the capability to correct single error, detect double error, and detect an error of three bits or more in a single b bit block.
As conventional methods for correcting and detecting errors, methods have been proposed:
(1) the method using the code which uses the b.times.b matrix, in which the b.times.b unit matrix is cyclically displaced along the column direction, as shown in the Japanese patent application publication No. 20142 of 1984; PA1 (2) the method using the code described in the thesis titled "Byte error detecting code for semiconductor storage device" by Kaneda in the Electronic Communication Society Journal Vol. J 67 to D No. 5 (May, 1984) and PA1 (3) the method using the code described in the thesis titled "Error-Correcting Codes for Semiconductor Memory Applications: A State-of-the-Art Review" (p. 129) by C. L. Chen and M. Y. Hsiao in the IMB J. Res. Develop., Vol. 28, No. 2 (March, 1984).
However, in these methods for correcting and detecting errors, the expansion of coded data length is not taken into consideration by using the general-purpose encoding and decoding LSI, for example, by constituting each coding and decoding circuit for different information having the data length of 2 bytes, 4 bytes, and 8 bytes, respectively.
According to the method mentioned above in (1), when the number of cyclic displacement in terms of the b.times.b unit matrix is S, the check bit number .gamma. is limited as follows: EQU .gamma.=S.multidot.b(s.gtoreq.2)
Therefore, the method was inadequate for correcting and detecting errors using the same check bit number .gamma. as that used in the conventional method using the SEC-DED code for each information having a data length of 2 bytes, 4 bytes, and 8 bytes, EQU 2-byte data length: .gamma.=6 EQU 4-byte data length: .gamma.=7 EQU 8-byte data length: .gamma.=8,
for example, a method for correcting and detecting errors using the SEC-DED-SbED code of b=4.
In the method mentioned in (2) there is an advantage that the data length can be expanded in this method compared with the other methods having the same check bit number, .gamma.. However, the SEC-DED-SbED code parity matrix is in such a form that the check bits are not centralized in a specific block and that they co-exist together with data bits in a same block. Consequently, the configuration of the coding and decoding circuits becomes complex when the coded data length is expanded. FIGS. 14A and 14B show an example of a parity matrix of 2-byte data length of b=4 (coded data length n=22 bits, data bit number K=16 bits) and an example of a parity matrix of 4-byte data length of b=4 (n=29, K=32), respectively. In these figures, S0 to S6 denote a syndrome, C0 to C6 denote check bits, and d0 to d31 denote data bits. The partial matrices, M0j and M1j, have a similar configuration so that their encoding and decoding circuits resemble each other. However, a partial matrix which resembles the partial matrix M04 is not present in the expanded part because the check bits C0 to C3 co-exist with data bits in the same block. The part marked with an asterisk (*) of the partial matrices, M01 and M11 and M03 and M13, represents a check bit and data bit, respectively, thus preventing the similarity of the encoding and decoding circuits and making the configuration of these circuits more complex.
In the method described above in (3), there is no similarity between the parity matrix of 4-byte data length (n=40, K=32) and these parity matrix of 8-byte data length (n=72, K=64). Further, it is impossible to construct a parity matrix of 2-byte data length (n=22, K=16) by shortening the parity matrix of the data length of 8 bytes while maintaining b=4.
If it is possible to construct encoding and decoding circuits using the common general-purpose encoding and decoding LSI for each of the storage devices of 2-byte data length, the storage device of 4-byte data length, and the storage device of the 8-byte data length, it is evidently possible to realize a method for correcting and detecting errors using the SEC-DED-SbED code at low cost owing to the mass production and reduction of the parts control processes that are enabled by the above LSI.